package sort;

import java.util.Arrays;

/**
 * @Author leecho
 * @Date: 2021/10/19 13:40
 * @Version 1.0
 */

public class QuickSort {
    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
//        int[] arr = {-9,78,0,23,-567,70};

        int[] arr = new int[80000];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random()*80000);
        }
        quickSort.quickSort(arr,0,arr.length-1);

        System.out.println(Arrays.toString(arr));
    }


    /*
    * 思路
    * - 传入的数组进行排序
    * - 找到中值，设定两个指向为传入数组的最左边和最右边
    * - 当左边比中值大的时候向前移动，右边比中值小的向前移动
    * - 当不满足条件停止的时候，两个指向两两相互交换
    * - 最后进行递归
    *   - 左递归
    *   - 有递归
    * */
    public void quickSort(int[] arr, int left, int right){
        int l = left;
        int r = right;
        int pivot = arr[(left+right) / 2];
        int temp = 0;

        while ( l < r){
            while (arr[l] < pivot){
                l++;
            }

            while (arr[r] > pivot){
                r--;
            }

            if (l > r)
                break;

            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            if (arr[r] == pivot){
                r--;
            }

            if (arr[l] == pivot){
                l++;
            }
        }

        if (l == r){
            l++;
            r--;
        }
        if (left < r)
            quickSort(arr,left,r);
        if (right > l)
            quickSort(arr,l,right);
    }
}
